Partitioning is a well known problem in image processing and computer vision. When an image is partitioned each pixel is assigned to one of a multiplicity of domains. In conventional partitioning methods, domain membership is determined by similarity or dissimilarity criteria.
More recently, several methods using two-dimensional image models and global optimization have been developed. Model based partitioning schemes approximate the pixels of each domain with an analytic intensity function. The analytic functions universally used for this purpose are two-dimensional polynomials. Since third order polynomials are sufficient to provide boundary continuity in both the function and its derivative they are typically the largest used.
Model based partitioning methods begin with an initial "seed" partition and make successive transformations that balance model complexity against model fidelity. Model complexity criteria include domain count and domain shape. Model fidelity is typically measured on a per pixel basis with each pixel's actual value being compared with its corresponding modeled value. An overall fidelity measure is obtained by aggregating the individual errors.
For example, a common partitioning operation is domain merge. When two domains are merged, model complexity is reduced since there are fewer domains and less domain periphery. Model fidelity suffers, however, since the combined domain's pixels, formerly modeled with two polynomials, must be modeled with one. The goal of the partitioning process is to make a sequence of transformations that results in a model with an overall balance of complexity and fidelity.
Unfortunately, the problem of determining a transformation's impact on model fidelity is computationally expensive. In many situations the square of the error between each pixel and its modeled value is an appropriate base for fidelity computations. If so, least squares methods can be used to reduce computational complexity.
Least Squares Methods
The principles of least squares data modeling are best illustrated by the widely used linear regression technique. Linear regression is method for fitting data points to a straight line model EQU y(x)=mx+b. (1)
The model obtained is optimal in the sense that the sum of the squared error between it and the data points ##EQU1## is minimal. Since a local extremum exists where partial derivatives of the error metric are equal to zero, the model parameters can be found by differentiating with respect to each parameter and solving the resulting system of equations ##EQU2##
An important aspect of the least squares error metric is that a solution for the model parameters b and m and the minimum error E can be formulated solely in terms of ensemble statistics. If the following sums are defined ##EQU3## then b and m are calculated as follows ##EQU4## and E is EQU E=S.sub.y.spsb.2 -2(mS.sub.xy +bS.sub.y)+2bmS.sub.x +m.sup.2 S.sub.x.spsb.2 +b.sup.2 S. (6)
By formulating the desired result in terms of ensemble statistics, a data point can be added to the set being modeled by simply adding to the ensembles EQU S:=S+1 S.sub.x :=S.sub.x +x.sub.i S.sub.y :=S.sub.y +y.sub.i S.sub.x.spsb.2 :=S.sub.x.spsb.2 +x.sub.i.sup.2 S.sub.xy :=S.sub.xy +x.sub.i y.sub.i S.sub.y.spsb.2 :=S.sub.y.spsb.2 +y.sub.i.sup.2, (7)
and the new optimum model parameters can be recalculated using (5). Points can be removed from the data set using an analogous subtraction procedure. The key idea is that no matter how many points are being modeled, a point can be added or subtracted and new model parameters calculated using only a fixed number of mathematical operations.
The ensemble technique can be extended to higher order polynomials and many other types of approximating functions. In the general least squares problem the systems of equations derived from differentiation with respect to model parameters are called the normal equations and are commonly represented in matrix form as EQU A.multidot.x=b. (8)
For example the normal equations for the model function EQU y(x)=ax.sup.2 +bx+c (9)
are ##EQU5##
Like any other matrix equation, the normal equations can be solved with standard matrix solution techniques such as Gauss-Jordan elimination or LU decomposition and back substitution. Also, since A is symmetric and positive the Cholesky factorization is applicable. By taking advantage of symmetry, the Cholesky method requires only one half of the number of mathematical operations required by the fastest general elimination technique.
Unfortunately, A is often singular, or nearly so, and standard techniques yield incorrect results. The singular value decomposition is the most widely used technique for solving singular systems. However, on small matrices such as the normal equations the singular value decomposition requires significantly more computation than standard techniques.